package dataStruct;

/**
 * @Author wangtengyu
 * @Create 2018-03-23-9:35
 * 自定义单向链表  单向链表只提供链表头插入
 */
public class SingleLinkedList {

    //头节点
    private Node head;
    //链表长度
    private int size;

    //链表有每一个节点组成
    private class Node {
        private Object data;
        private Node next;

        public Node(Object data) {
            this.data = data;
        }
    }

    public SingleLinkedList() {
        size = 0;
        head = null;
    }

    /**
     * 在链表头添加元素
     *
     * @param obj
     * @return
     */
    public Object addHead(Object obj) {
        Node newHead = new Node(obj);
        if (size == 0) {
            head = newHead;
        } else {
            newHead.next = head;
            head = newHead;
        }
        size++;
        return obj;
    }

    /**
     * 在链表头删除元素
     *
     * @return
     */
    public Object deleteHead() {
        Object removeData = null;
        while (size > 0) {
            if (size == 1) {
                removeData = head.data;
                head = null;
            } else {
                removeData = head.data;
                head = head.next;
            }
            size--;
        }
        return removeData;
    }


    /**
     * 查找指定元素 找到了返回节点 找不到返回null  查找不涉及到链表真实的长度变动 所以定义一个tempSize
     *
     * @param obj
     * @return
     */
    public Node find(Object obj) {
        Node currentNode = head;
        int tempSize = size;
        while (tempSize > 0) {
            if (currentNode.data.equals(obj)) {
                return currentNode;
            } else {
                currentNode = head.next;
            }
            tempSize--;
        }

        return null;

    }


    /**
     * 删除指定元素 删除成功返回true 删除涉及链表真是的长度变动 所以用size
     *
     * @param obj
     * @return
     */
    public boolean delete(Object obj) {
        if (size == 0) {
            return false;
        }
        Node currentNode = head;
        Node previousNode = head;
        while (currentNode.data != obj) {
            if (currentNode.next == null) {
                return false;
            }
            previousNode = currentNode;
            currentNode = currentNode.next;
        }

        //如果删除的是第一个节点
        if (currentNode == head) {
            head = currentNode.next;
        } else {
            previousNode.next = currentNode.next;
        }
        size--;
        return true;
    }

    /**
     * 返回头节点存储的元素
     *
     * @return
     */
    public Object returnHead() {
        return head.data;
    }

    /**
     *
     */


    /**
     * 判断是否为空
     */
    public boolean isEmpty() {
        return (size == 0);
    }


    /**
     * 显示节点信息
     */
    public void display() {
        if (size > 0) {
            Node node = head;
            int tempSize = size;
            if (tempSize == 1) {//当前链表只有一个节点
                System.out.println("[" + node.data + "]");
                return;
            }
            while (tempSize > 0) {
                if (node.equals(head)) {
                    System.out.print("[" + node.data + "->");
                } else if (node.next == null) {
                    System.out.print(node.data + "]");
                } else {
                    System.out.print(node.data + "->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();

        } else {
            System.out.println("");
        }
    }


    public static void main(String[] args) {
        SingleLinkedList singleList = new SingleLinkedList();
        singleList.addHead("A");
        singleList.addHead("B");
        singleList.addHead("C");
        singleList.addHead("D");
        //打印当前链表信息
        singleList.display();
        //删除C
        singleList.delete("C");
        singleList.display();
        //查找B
        System.out.println(singleList.find("B"));
    }


}
